#include <stdio.h>
#include <stdlib.h>



void print_matrix_chain_order(void *vp, int n, int i, int j) {
    typedef int IA[n];
    IA *S = vp;
    if(i<j) {
        putchar('(');
        print_matrix_chain_order(vp, n, i, S[i][j]);
        print_matrix_chain_order(vp, n, S[i][j]+1, j);
        putchar(')');
    }else if(i==j) {
        printf("M%d", i);
    }
}

void matrix_chain_order(int *p, int n) {
    int P[n][n];
        /*****************
        P[i][j]: mx[i]*mx[i+1]...mx[j]的最少乘法计算次数
        mx[i] = (p[i-1], p[i])
        *****************/
    int S[n][n]; 
        //S[i][j]: mx[i]*mx[i+1]...mx[j]的具有最少乘法计算次数的计算顺序最后一乘的节点
    int i, j, k;
    int len;
    int cur_value;
    for(i=1; i<n; i++) {
        P[i][i] = 0;
    }
    /**************
        当j>i>0时有
        P[i][j] =  min(P[i][i]+mx[i].m*mx[i].n*mx[j].n+P[i+1][j], 
                       P[i][i+1]+mx[i].m*mx[i+1].n*mx[j].n+P[i+2][j]...
                       P[i][j-1]+mx[i].m*mx[j-1].n*mx[j].n+P[j][j]) 
                = min(P[i][i]+p[i-1]*p[i]*p[j]+P[i+1][j],
                      P[i][i+1]+p[i-1]*p[i+1]*p[j]+P[i+2][j]...
                      P[i][j-1]+p[i-1]*p[j-1]*p[j]+P[j][j])
    **************/
    for(len=2; len<n; len++) {
        for(i=1; i<n-len+1; i++) {
            j = i+len-1;
            S[i][j] = i;
            P[i][j] = P[i][i]+p[i-1]*p[i]*p[j]+P[i+1][j];
            for(k=i+1; k<j; k++){
                cur_value = P[i][k]+p[i-1]*p[k]*p[j]+P[k+1][j];
                if(cur_value < P[i][j]) {
                    P[i][j] = cur_value;
                    S[i][j] = k;
                }
            }
        }
    }
    printf("multi counts: %d\n", P[1][n-1]);
    print_matrix_chain_order(S, n, 1, n-1);
    putchar('\n');

    
}

int main(void) {
    int p[] = {5, 10, 3, 12, 5, 50, 6};
    matrix_chain_order(p, 7);
    return 0;
}

